//https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int begin = 0;
        int end = nums.size() - 1;

        while (begin < end)
        {
            while (begin < end && nums[begin] % 2 == 1)
                ++begin;

            while (begin < end && nums[end] % 2 == 0)
                --end;

            swap(nums[begin], nums[end]);
        }

        return nums;
    }
};